#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class State{
public:
	int weapons;
	int shots;
	bool operator < (const State &A) const {
		return this->shots > A.shots;
	}
};

class KiloManX {
public:
	int leastShots(vector <string>, vector <int>);
	bool visited[1<<15];
	int N;
};

int KiloManX::leastShots(vector <string> damageChart, vector <int> bossHealth) {
	memset(visited, false, sizeof(visited));
	N = damageChart.size();
	priority_queue<State> q;
	State state = {0, 0};
	q.push(state);
	while(!q.empty()){
		State s = q.top();
		q.pop();
		
		if(visited[s.weapons]) continue;
		visited[s.weapons] = true;
		
		if(s.weapons == (1<<damageChart.size())-1) return s.shots;
		
		for(int i=0; i<damageChart.size(); i++){
			if((s.weapons>>i) & 1) continue;
			int best = bossHealth[i];
			for(int j=0; j<damageChart.size(); j++){
				if(i==j) continue;
				if(((s.weapons>>j) & 1) && damageChart[j][i]!='0'){
					int shotNeeded = (bossHealth[i] + damageChart[j][i] - '1') / (damageChart[j][i] - '0');
					best = min(best, shotNeeded);
				}
			}
			State tmp = {s.weapons | (1<<i), s.shots + best};
			q.push(tmp);
		}
	}
	return -1;
}


double test0() {
	string t0[] = {"070","500","140"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	int t1[] = {150,150,150};
	vector <int> p1(t1, t1+sizeof(t1)/sizeof(int));
	KiloManX * obj = new KiloManX();
	clock_t start = clock();
	int my_answer = obj->leastShots(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p2 = 218;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test1() {
	string t0[] = {"1542", "7935", "1139", "8882"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	int t1[] = {150,150,150,150};
	vector <int> p1(t1, t1+sizeof(t1)/sizeof(int));
	KiloManX * obj = new KiloManX();
	clock_t start = clock();
	int my_answer = obj->leastShots(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p2 = 205;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test2() {
	string t0[] = {"07", "40"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	int t1[] = {150,10};
	vector <int> p1(t1, t1+sizeof(t1)/sizeof(int));
	KiloManX * obj = new KiloManX();
	clock_t start = clock();
	int my_answer = obj->leastShots(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p2 = 48;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test3() {
	string t0[] = {"198573618294842",
 "159819849819205",
 "698849290010992",
 "000000000000000",
 "139581938009384",
 "158919111891911",
 "182731827381787",
 "135788359198718",
 "187587819218927",
 "185783759199192",
 "857819038188122",
 "897387187472737",
 "159938981818247",
 "128974182773177",
 "135885818282838"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	int t1[] = {157, 1984, 577, 3001, 2003, 2984, 5988, 190003,
9000, 102930, 5938, 1000000, 1000000, 5892, 38};
	vector <int> p1(t1, t1+sizeof(t1)/sizeof(int));
	KiloManX * obj = new KiloManX();
	clock_t start = clock();
	int my_answer = obj->leastShots(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p2 = 260445;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test4() {
	string t0[] = {"02111111", "10711111", "11071111", "11104111",
 "41110111", "11111031", "11111107", "11111210"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	int t1[] = {28,28,28,28,28,28,28,28};
	vector <int> p1(t1, t1+sizeof(t1)/sizeof(int));
	KiloManX * obj = new KiloManX();
	clock_t start = clock();
	int my_answer = obj->leastShots(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p2 = 92;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}

int main() {
	int time;
	bool errors = false;
	
	time = test0();
	if (time < 0)
		errors = true;
	
	time = test1();
	if (time < 0)
		errors = true;
	
	time = test2();
	if (time < 0)
		errors = true;
	
	time = test3();
	if (time < 0)
		errors = true;
	
	time = test4();
	if (time < 0)
		errors = true;
	
	if (!errors)
		cout <<"You're a stud (at least on the example cases)!" <<endl;
	else
		cout <<"Some of the test cases had errors." <<endl;
}

//Powered by [KawigiEdit] 2.0!
